package algotithm.leetcode.listnode.test445;

import algotithm.leetcode.listnode.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/20-16:57
 * @URL https://leetcode-cn.com/problems/add-two-numbers-ii/
 * @Title 445. 两数相加 II
 */
public class Solution {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(7);
        ListNode n1 = new ListNode(2);
        ListNode n2 = new ListNode(4);
        ListNode n3 = new ListNode(3);
        l1.next = n1;
        n1.next = n2;
        n2.next = n3;
        n3.next = null;

        ListNode l2 = new ListNode(5);
        ListNode m1 = new ListNode(6);
        ListNode m2 = new ListNode(4);
        l2.next = m1;
        m1.next = m2;
        m2.next = null;

        Solution solution = new Solution();
        ListNode listNode = solution.addTwoNumbers(l1, l2);
        while (listNode != null ) {
            System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> stack1 = new ArrayDeque<>();
        Deque<Integer> stack2 = new ArrayDeque<>();
        while (l1 != null) {
            stack1.push(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.val);
            l2 = l2.next;
        }
        // ListNode dummy = new ListNode(-1);
        int carry = 0;
        ListNode ans = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
            int n = stack1.isEmpty() ? 0 : stack1.pop();
            int m = stack2.isEmpty() ? 0 : stack2.pop();
            carry += n + m;
            ListNode cur = new ListNode(carry % 10);
            carry /= 10;
            cur.next = ans;
            ans = cur;
        }
        return ans;
    }
}